package com.leetcode.partition10;

/**
 * @author `RKC`
 * @date 2021/9/17 9:20
 */
public class LC918环形子数组的最大和 {

    public static int maxSubarraySumCircular(int[] nums) {
        return dynamicProgramming(nums);
    }

    public static void main(String[] args) {
        int[] nums = {2, -3, -2, 1, -5};
        System.out.println(minimumSubarray(nums));
    }

    private static int dynamicProgramming(int[] nums) {
        //两种情况，一种是没有跨界的情况，另一种为跨界的情况；没有跨界直接对子数组求最大和即可，跨界情况=数组和-没有跨界的最小子数组和
        //没有跨界时求出子数组的最大和
        int maxSum1 = maximumSubarray(nums), sum = 0, maxSum2;
        boolean flag = true;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (nums[i] > 0) flag = false;
        }
        if (flag) maxSum2 = minimumSubarray(nums);
        else maxSum2 = sum - minimumSubarray(nums);     //跨界的情况
        System.out.println("sum1=" + maxSum1 + "  sum2=" + maxSum2);
        return Math.max(maxSum1, maxSum2);
    }

    private static int maximumSubarray(int[] nums) {
        //动态规划
//        int[] dp = new int[nums.length];
//        dp[0] = nums[0];
//        int answer = dp[0];
//        for (int i = 1; i < nums.length; i++) {
//            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
//            answer = Math.max(answer, dp[i]);
//        }
//        System.out.println("最大子数组和：" + answer);
        //贪心算法
        int answer = Integer.MIN_VALUE, cur = 0;
        for (int i = 0; i < nums.length; i++) {
            cur += nums[i];
            answer = Math.max(cur, answer);
            if (cur < 0) cur = 0;
        }

        return answer;
    }

    private static int minimumSubarray(int[] nums) {
//        int[] dp = new int[nums.length];
//        dp[0] = nums[0];
//        int answer = dp[0];
//        for (int i = 1; i < nums.length; i++) {
//            dp[i] = Math.min(dp[i - 1] + nums[i], nums[i]);
//            answer = Math.min(answer, dp[i]);
//        }
//        System.out.println("最小子数组和：" + answer);
        int answer = Integer.MAX_VALUE, cur = 0;
        for (int i = 0; i < nums.length; i++) {
            cur += nums[i];
            answer = Math.min(cur, answer);
            if (cur > 0) cur = 0;
        }
        return answer;
    }
}
